package 完全背包问题;

import java.util.Scanner;

/**
 * @Date 2024/6/3 16:28
 * @description: 牛客42: 完全背包模版
 * .            https://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc
 * @Author LittleNight
 */
public class niuke {

    // 空间优化版本
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别

        int n, V;
        int[] v, w;
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            n = in.nextInt();  V = in.nextInt();
            v = new int[n + 1]; w = new int[V + 1];
            // 注意物品从 1 开始
            for(int i = 1; i <= n; i++) {
                v[i] = in.nextInt(); w[i] = in.nextInt();
            }

            // 第一问, 不超过问题, 无需初始化, j 从 0 开始
            // 注意本来物品就是从1开始的, 不用映射
            // 表示前 i 个数中, 任挑一些数, 背包容量不超过 j 时, 最大的和是多少
            int[] dp = new int[V + 1];
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= V; j++) { // 第二个for 循环还是从左往右
                    // 不选第 i 个物品
                    dp[j] = dp[j];
                    // 选第 i 个物品 (方程推导看视频)
                    if (j - v[i] >= 0) {
                        // dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i]] + w[i - 1]);
                        dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
                    }
                }
            }
            System.out.println(dp[V]);
            // return dp[n][V];


            // 第二问. 正好, 需要初始化第一行为 -1
            // 这个主要填充一维数组
            // Arrays.fill(dp, 0);
            for (int i = 0; i <= n; i++)
                for (int j = 0; j <= V; j++)
                    dp[j] = 0;

            for(int j = 1; j <= V; j++) dp[j] = -1;
            // 填表, 从上往下, 从左往右
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= V; j++) {
                    // 不选第 i 个物品
                    dp[j] = dp[j];
                    // 选第 i 个物品 (方程推导看视频)
                    if (j - v[i] >= 0 && dp[j - v[i]] != -1) {
                        dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
                    }
                }
            }
            int x = dp[V];
            System.out.println(x == -1 ? 0 : x);
        }
    }

    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别

        int n, V;
        int[] v, w;
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            n = in.nextInt();  V = in.nextInt();
            v = new int[n + 1]; w = new int[V + 1];
            // 注意物品从 1 开始
            for(int i = 1; i <= n; i++) {
                v[i] = in.nextInt(); w[i] = in.nextInt();
            }

            // 第一问, 不超过问题, 无需初始化, j 从 0 开始
            // 注意本来物品就是从1开始的, 不用映射
            // 表示前 i 个数中, 任挑一些数, 背包容量不超过 j 时, 最大的和是多少
            int[][] dp = new int[n + 1][V + 1];
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= V; j++) {
                    // 不选第 i 个物品
                    dp[i][j] = dp[i - 1][j];
                    // 选第 i 个物品 (方程推导看视频)
                    if (j - v[i] >= 0) {
                        // dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i]] + w[i - 1]);
                        dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i]] + w[i]);
                    }
                }
            }
            System.out.println(dp[n][V]);
            // return dp[n][V];


            // 第二问. 正好, 需要初始化第一行为 -1
            // 这个主要填充一维数组
            // Arrays.fill(dp, 0);
            for (int i = 0; i <= n; i++)
                for (int j = 0; j <= V; j++)
                    dp[i][j] = 0;

            for(int j = 1; j <= V; j++) dp[0][j] = -1;
            // 填表, 从上往下, 从左往右
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= V; j++) {
                    // 不选第 i 个物品
                    dp[i][j] = dp[i - 1][j];
                    // 选第 i 个物品 (方程推导看视频)
                    if (j - v[i] >= 0 && dp[i][j - v[i]] != -1) {
                        dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i]] + w[i - 1]);
                    }
                }
            }
            int x = dp[n][V];
            System.out.println(x == -1 ? 0 : x);
        }
    }
}
